package linkedlist.other;

import linkedlist.Node;
import linkedlist.create.LoopLinkedCreator;

import java.util.Arrays;

/**
 * @Author wangtengyu
 * @Create 2018-09-06-9:09 删除倒数第k个节点 思路 共有n个节点，倒数第k个节点前的节点数，有n-k个，倒数第k个节点就是第n-k+1个节点
 * <p>
 * 1.遍历第一次，求的总节点数量，然后再遍历一次，得到第n-k+1个节点 2.定义两个指针，第一个指针先走k-1步，第二个指针再走，第一个指针停止的时候，第二个指针就在倒数第k个节点上
 * 实际上，第一个指针走到末尾时，第二个指针走的是n-（k-1）步，实际上就是在n-k+1的地方
 *
 *
 *
 * 健壮性的判断 1.head不为空 2.k要大于等于1 3.k的长度不能超过链表的长度
 */
public class FindReverseKNode {

  /**
   * 两次遍历的方法
   */
  public Node findKNode(Node head, int k) {
    if (head == null) {
      return null;
    }

    if (k <= 0) {
      return null;
    }

    //第一次遍历，统计数量
    int count = 0;
    Node countNode = head;
    while (countNode != null) {
      count++;
      countNode = countNode.getNext();
    }
    //第二次遍历
    if (k > count) {
      return null;
    }
    int step = count - k + 1;
    Node K = null;
    Node newHead = head;
    for (int i = 0; i < step; i++) {
      K = newHead;
      newHead = newHead.getNext();
//            K=head;
//            K=K.getNext();
    }
    return K;
  }


  /**
   * @param head
   * @param k
   * @return
   */
  public Node findKNode2(Node head, int k) {
    if (head == null) {
      return null;
    }
    if (k <= 0) {
      return null;
    }

    Node p1 = head;
    Node p2 = head;

    for (int step = k - 1; step > 0; step--) {
      if (p1.getNext() != null) {
        p1 = p1.getNext();
      } else {
        return null;
      }
    }

    while (p1.getNext() != null) {
      p2 = p2.getNext();
      p1 = p1.getNext();
    }

    return p2;


  }


  public static void main(String[] args) {
    LoopLinkedCreator creator = new LoopLinkedCreator();
    FindReverseKNode findReverseKNode = new FindReverseKNode();
    Node head = creator.createlinkedList(Arrays.asList(1, 2, 3, 4, 5));
//        Node k=findReverseKNode.findKNode(head,1);
    Node k = findReverseKNode.findKNode(head, 4);
    if (k == null) {
      System.out.println("链表为空或者链表长度不满足查询条件");
    } else {
      System.out.println(k.getData());
    }

  }


}
